package Heap;

import com.sun.org.apache.xml.internal.security.utils.HelperNodeList;

import java.util.Arrays;

public class TestHeap {

    public static int[] elem;
    public static int usedSize;

    public TestHeap (int[] arr) {
        this.elem = Arrays.copyOf(arr, arr.length);
        usedSize = arr.length;
    }
    public TestHeap () {
        this.elem = new int[11];
        usedSize = 0;
    }

    public static void creatHeap (int[] arr) {
        //root = 最后一个非叶子结点
        int root = (usedSize-2) / 2;
        while (root >= 0) {
            shiftDown(arr, root);
            root--;
        }
    }

    private static void shiftDown (int[] arr, int root) {
        //child为左孩子
        int child = root*2 +1;
        /**
         * child存在
         * 但是child+1（右孩子不一定存在啊）
         */
        while (child < usedSize) {
            /**
             * 保持右孩子是最小的
             * 将右孩子赋值给child
             * 右孩子存在 && 右孩子比左孩子大
             */
            if (child + 1 < usedSize && arr[child] > arr[child + 1]) {
                swap(arr, child, child + 1);
                child++;
            }
            //最小孩子比根结点小：交换
            if (arr[child] < arr[root]) {
                swap(arr, child, root);
            } else {
                break;
            }
        }
    }

    public static void swap (int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public void offer (int data) {
        if (isFull()) {
            if (elem.length < 64) {
                elem = Arrays.copyOf(elem, elem.length * 2);
            } else {
                elem = Arrays.copyOf(elem, elem.length + elem.length >> 1);
            }
        }
        elem[usedSize] = data;
        shiftUp(elem, usedSize);
    }

    private void shiftUp (int[] arr, int child) {
        //循环直到child为根结点
        while (child > 0) {
            int parent = (child - 1)/ 2;
            //child是parent的右孩子
            if ((child % 2) == 0) {
                //右孩子比左孩子大：交换
                if (elem[child] > elem[child - 1]) {
                    swap(arr, child, child - 1);
                }
            }
            if (elem[child] < elem[parent]) {
                swap(arr, child, parent);
                child = parent;
            } else {
                break;
            }
        }
    }

    public void poll () {
        //移除堆顶元素，堆尾元素移到栈顶，usedSize--
        elem[0] = elem[--usedSize];
        shiftDown(elem, 0);
    }

    public boolean isFull () {
        if (usedSize == elem.length) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1,4,5,6,2,7,3,8,10,9};
        TestHeap myHeap = new TestHeap(arr);
        creatHeap(arr);
        for (int x: arr) {
            System.out.print(x + " ");
        }
    }
}
